package 领扣算法.力扣计划.算法基础.二进制矩阵中的最短路径;

public class Main {
    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0]==1||grid[grid.length-1][grid[0].length-1]==-1)
            return -1;
        int[][] data=new int[grid.length+2][grid[0].length+2];
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data[0].length; j++) {
                data[i][j]=-1;
            }
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                data[i+1][j+1]=-grid[i][j];
            }
        }
        data[1][1]=1;
        boolean target=true;
        while (target){
            target=false;
            for (int i = 0; i < grid.length; i++) {
                int x=i+1;
                for (int j = 0; j < grid[0].length; j++) {
                    int y=j+1;
                    if (data[x][y]<0)
                        continue;
                    int min=plus(data,x,y);
                    if (data[x][y]==0&&min!=Integer.MAX_VALUE){
                        data[x][y]=min+1;
                        target=true;
                    }
                    else {
                        if (data[x][y]-1>min){
                            data[x][y]=min+1;
                            target=true;
                        }
                    }
                }

            }
        }
        int res=data[data.length-2][data[0].length-2];
        if (res==Integer.MAX_VALUE||res==0)
            return -1;
        else
            return data[data.length-2][data[0].length-2];
    }

    private int plus(int[][] data, int i, int j) {
        int min = Integer.MAX_VALUE;
        int target=0;
        target=data[i-1][j];
        if (target>0){
            min=Math.min(min,target);
        }
        target=data[i-1][j-1];
        if (target>0){
            min=Math.min(min,target);
        }
        target=data[i-1][j+1];
        if (target>0){
            min=Math.min(min,target);
        }
        target=data[i][j-1];
        if (target>0){
            min=Math.min(min,target);
        }
        target=data[i][j+1];
        if (target>0){
            min=Math.min(min,target);
        }
        target=data[i+1][j-1];
        if (target>0){
            min=Math.min(min,target);
        }
        target=data[i+1][j];
        if (target>0){
            min=Math.min(min,target);
        }
        target=data[i+1][j+1];
        if (target>0){
            min=Math.min(min,target);
        }

        return min;
    }
    public static void main(String arg[]){//main--来自高金磊

        new Main().shortestPathBinaryMatrix(new int[][]{{0,1},{1,0}});
    }
}
